package com.sicheng.algorithm.dynamic;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/10/25 10:20
 */
public class CompletePack {

    /**
     * 有N件物品和一个最多能背重量为W的背包。
     * 第i件物品的重量是weight[i]，得到的价值是value[i] 。
     * 每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
     */
    public static void main(String[] args) {

        int[] weights = {1, 3, 4};
        int[] values = {15, 20, 30};

        System.out.println(completePack(4, weights, values));
    }


    /**
     * 背包最大重量为4。
     * <p>
     * 物品为
     * 重量	价值
     * 物品0	1	15
     * 物品1	3	20
     * 物品2	4	30
     */

    public static int completePack(int packWeight, int[] weights, int[] values) {


        int[] dp = new int[packWeight + 1];
        for (int i = 1; i <= packWeight; i++) {//遍历背包容量
            for (int j = 0; j < weights.length; j++) {//遍历物品
                if (i >= weights[j])
                    dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
            }

        }

        return dp[dp.length - 1];
    }


}
